package datastructure;/*
 *  @类名: LinkList
 *  @作者:云建文 屈子涵 黄珂 孙烨
 *  @班级：2023级网络空间安全一班
 *  @时间:2024/10/30
 *  @描述:用单链表存储结构实现顺序表
 */
//单链表中的节点对象定义，要求必须有存储元素的数据成员data变量以及存储后继节点变量的指针成员next
class LinkNode<E>{
    //作者：屈子涵
    E data;//定义泛型变量 data作为数据成员
    LinkNode<E> next;//定义LinkNode<E>类的对象next来引用下一个节点
}
public class LinkList<E> {
    //作者：屈子涵
    //要求有成员变量：E类型对象头节点head
    LinkNode<E> head;
    //默认无参数构造方法要求创建一个头节点对象，并将头节点对象的next设置为null
    public LinkList(){
        head=new LinkNode<>();
        head.next=null;
    }
    //利用头插法：由数组a整体建立单链表
    //作者：屈子涵
    public void createListF(E[] a){
        for(E i:a)//遍历数组a中的每一个元素
        {
            LinkNode<E> xinjiedian=new LinkNode<>();//建立新节点
            xinjiedian.data=i;//为新节点的数据成员data赋值
            xinjiedian.next=head.next;//新节点的指针成员为null空
            head.next=xinjiedian;//头节点的指针成员为新节点 把新节点接在头节点后面
        }
    }
    //利用尾插法：由数组a整体建立单链表
    //作者：云建文
    public void createListR(E[] a){
        LinkNode<E> rear=head;
        for(E i:a){
            LinkNode<E> xinjiedian=new LinkNode<>();
            xinjiedian.data=i;
            xinjiedian.next=rear.next;
            rear.next=xinjiedian;
            rear=xinjiedian;
        }
    }
    //在线性表的末尾添加一个元素e
    //作者：屈子涵
    public void add(E e){
        LinkNode<E> xinjiedian=new LinkNode<>();
        xinjiedian.data=e;
        LinkNode<E> zz=head;
        while(zz.next!=null){//while循环到尾节点
            zz=zz.next;
        }
        zz.next=xinjiedian;//尾节点的next成员引用新节点 即把新节点接到此时的尾节点上，这样新节点就成了新的尾节点
        xinjiedian.next=null;
    }
    //在线性表中序号i位置插入元素e
    //作者：云建文
    public void insert(int i, E e){
        LinkNode<E> zz=head;
        if(i<0||i>size()){
            throw new IllegalArgumentException("i参数不合法");//throw关键字抛出异常的抛出 IllegalArgumentException 传递给方法的参数不合法的异常
        }
        else {
            int count = 0;
            while (zz.next != null && count < i - 1)//while循环到序号i-1的位置 把新节点接在序号i-1的位置后 成为新的序号i的节点
            {
                zz = zz.next;
                count++;
            }
            LinkNode<E> xinjiedian = new LinkNode<>();
            xinjiedian.data = e;
            xinjiedian.next = zz.next;
            zz.next = xinjiedian;
        }
    }
    //求线性表的长度
    //作者：屈子涵
    public int size(){
        int count=0;//定义count变量来计数
        LinkNode<E> zz=head;//定义“指针”zz；
        while(zz.next!=null){//while循环到尾节点 count变量的值就是链表的长度
            zz=zz.next;
            count++;
        }
        return count;
    }
    //返回序号为i的结点
    //作者：云建文
    private LinkNode<E> geti(int i){
        int count=0;
        LinkNode<E> zz=head;
        while(zz.next!=null&&count<i){
            zz=zz.next;
            count++;
        }
        if(i<0||i>size()){
            throw new IllegalArgumentException("i参数不合法");
        }
        else return zz;
    }
    //返回线性表中序号为i的元素
    //作者：云建文
    public E getElem(int i){
        int count=0;
        LinkNode<E> zz=head;
        while(zz.next!=null&&count<i){
            zz=zz.next;
            count++;
        }
        if(i<0||i>size()){
            throw new IllegalArgumentException("i参数不合法");
        }
        else return zz.data;
    }

    //查找第一个为e的元素的序号
    //作者：云建文
    public int getNo(E e){
        LinkNode<E> zz=head.next;//从第一个节点开始寻找，因为头节点的data为null，用equals()方法会报错
        int count=1;
        while(zz.next!=null&&!zz.data.equals(e)){
            zz=zz.next;
            count++;
        }
        if(zz.data.equals(e)){
            return count;
        }
        else {
            System.out.printf("没有为%d的元素！\n", e);
            return -1;
        }
    }

    //设置线性表的长度:用于缩小线性表的长度，当参数nlen错误时（nlen<0或者nlen>n），抛出相应的异常，
    // 若nlen等于原单链表长度，直接返回，
    // 否则找到序号为nlen-1的结点p，将其置为尾结点，使新单链表的长度为nlen。
    //作者：云建文
    public void setSize(int nlen){
        int len=size();
        if(nlen<0||nlen>len){
            throw new IllegalArgumentException("nlen参数错误");
        }
        else if(nlen==len){
            return;
        }
        else{
            int count=0;
            LinkNode<E> zz=head;
            while(count!=nlen-1)
            {
                zz=zz.next;
                count++;
            }
            LinkNode<E> p=zz.next;
            p.next=null;
        }
    }

    //设置序号i的元素为e
    //作者：云建文
    public void setElem(int i,E e){
        int count=0;
        LinkNode<E> zz=head;
        if(i<0||i>size()){
            throw new IllegalArgumentException("i参数错误");
        }
        else{
            while(count!=i)
            {
                zz=zz.next;
                count++;
            }
            zz.data=e;
        }
    }
    //交换序号i和序号j的元素
    //作者：云建文
    public void swap(int i,int j){
        E temp;
        LinkNode<E> zzi=geti(i);//获得i位置的节点 让zzi对象引用
        LinkNode<E> zzj=geti(j);
        if(zzi==null||zzj==null){
            throw new IllegalArgumentException("i参数或j参数错误");
        }
        else{
            temp=zzi.data;
            zzi.data=zzj.data;
            zzj.data=temp;
        }
    }
    //在线性表中删除序号i位置的元素
    //作者：屈子涵
    public void delete(int i){
        int count=0;
        LinkNode<E> zz=head;
        if(i<0||i>size()){
            throw new IllegalArgumentException("i参数错误");
        }
        while(count<i-1)//while循环到序号i-1位置的节点 i-1节点next成员引用的是i节点 i节点的next成员引用的是i+1
        {
            zz=zz.next;
            count++;
        }
        zz.next=zz.next.next;//把i+1节点接在i-1节点后面 跳过i节点 就相当于删除了i节点
    }
    //输出链表中的所有元素
    //作者：黄珂 孙烨
    public void PrintOut(){
        LinkNode<E> zz=head;
        while(zz.next!=null){
            zz=zz.next;
            System.out.print(zz.data+" ");
        }
        System.out.println();
    }
}